Electronic design automation (EDA) uses software tools for design and analysis of complex digital electronic systems such as printed circuit boards (PCBs) and integrated circuits (ICs). So as to ensure correct operability of a complicated digital electronic circuit design before significant investment is committed in the physical fabrication of chips or boards that use the design, and thus to avoid substantial waste and retooling, prior to fabrication of the design, a design can be required to pass a series of verification tests collectively referred to as “signoff.” Signoff is accomplished in part by the performance of static timing analyses (STA), used in EDA tools to assess the timing of a digital circuit design, generally using software techniques and models that yield operational timing characteristics of the digital circuit design to discover, and thereby to correct through design modification, timing violations in a circuit being analyzed. Because design optimization to fix detected violations following STA frequently results in creating more violations, signoff typically involves numerous repeated iterations of remedial transformations of the circuit design. The use of pessimistic timing characteristics in STA disadvantageously results in false-positive violations, requiring costly over-fixing and wastefully increasing turnaround time, which in turn fails to minimize fabricated circuit product cost, time to market, power requirements, and substrate area, while maximizing circuit performance.
STA generally includes a plurality of different static timing analysis methodologies variously performing different algorithmic checks on the circuit design with attendant accuracy versus runtime tradeoffs for each. Examples of STA analyses include graph-based analysis (GBA), which performs timing analysis on a node-by-node level, traversing exhaustively throughout the circuit design, and path-based analysis (PBA), which performs algorithmic checks on the circuit design that are less pessimistic than with GBA in that they do not incorporate the same worst-case-scenario assumptions, and thereby do not result in generating the same false-positive violations. PBA requires greater runtime, memory footprint, storage footprint, and processing resources than GBA. Accordingly, GBA is generally used as a coarse filter to approve timing paths that clearly do not have timing violations, and PBA is subsequently used only on the unapproved timing paths, as a slower but finer filter to further winnow out timing paths incorrectly detected by GBA as containing violations.
GBA generates a timing graph for a given netlist and then computes the worst arrival and required times on the nodes of the graph. For nodes that are sinks of a timing path, it also computes the worst slack, slack being the difference between a desired arrival time (as defined by the constraints; usually, synchronized with the arrival time of a second signal) and the actual arrival time of a signal propagated through a given path of the circuit design as defined by the netlist and other parameters. In doing so, worst-case timing paths in the circuit design are determined. GBA identifies timing paths with apparent timing violations, where the computed timing is not within the margins allowed by the constraints. GBA makes certain pessimistic assumptions about the behavior of each stage. For example, it may assume the input slew, i.e., the time it takes a signal to “ramp up” from “off” to “on,” or “ramp down” from “on” to “off,” to be at its worst for each gate within a timing path. Such pessimistic assumptions allow GBA computations to operate comparatively quickly, but at the cost of sometimes reporting a “false” timing violation where a more exact analysis would have shown that the timing path meets the constraints.
PBA peels a set of paths in non-increasing order of criticality and applies path-specific timing update to each of these paths. Path peeling, i.e., the process of determining paths between start points and endpoints in a network graph of a digital design (see FIG. 4 for a simplified example), is a computationally expensive process. By analyzing the path with reduced pessimism, many timing violations can be waived which in turn tells better timing signoff. Aside from this peeling, PBA otherwise performs similar computations to GBA, but takes into account the input slew and other variables that would actually be encountered in a timing path, rather than simply assuming the worst case slew of all inputs, as GBA pessimistically would. These more complex computations take considerably longer than those of GBA, and if applied to all paths in the circuit can require an unfeasible amount of runtime and processing power to approach completion. Combining GBA and PBA by performing them successively can return first a coarse timing report indicative of a GBA-violating zone, whereafter only timing paths with apparent timing violations according to GBA are re-analyzed under PBA, without the pessimism of GBA, to potentially determine that timing paths with apparent timing violations (as determined by GBA) do not, in fact, violate the provided constraints, and therefore do not require redesign, through what is known as an engineering change order (ECO).